package com.yan_jiu_sheng.LeetCodeHot100.AC;

/**
 * https://leetcode.cn/problems/partition-equal-subset-sum/description/?envType=study-plan-v2&envId=top-100-liked
 * 参考通过
 *
 * @author yulongtian
 * @create 2024-07-24 10:13
 */
public class Test87 {
    public static void main(String[] args) {
        System.out.println(new Test87().canPartition(new int[]{1, 5, 11, 5}));
//        System.out.println(new Test87().canPartition(new int[]{2, 3, 4, 5, 6}));
//        System.out.println(new Test87().canPartition(new int[]{1, 2, 3, 5}));
    }

    /*
    参考通过https://leetcode.cn/problems/partition-equal-subset-sum/solutions/442320/fen-ge-deng-he-zi-ji-by-leetcode-solution
     */
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return false;
        }
        int sum = 0, maxNum = 0;
        for (int num : nums) {
            sum += num;
            maxNum = Math.max(maxNum, num);
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        if (maxNum > target) {
            return false;
        }
        boolean[][] dp = new boolean[n][target + 1];
        for (int i = 0; i < n; i++) {
            dp[i][0] = true;
        }
        dp[0][nums[0]] = true;
        for (int i = 1; i < n; i++) {
            int num = nums[i];
            for (int j = 1; j <= target; j++) {
                if (j >= num) {
                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n - 1][target];
    }


//    /*
//    dfs方法正确，但超时了    通过36 / 143个测试用例
//     */
//    public boolean canPartition(int[] nums) {
//        int sum = 0;
//        for (int num : nums) {
//            sum += num;
//        }
//        return dfs(nums.length - 1, nums, sum, sum);
//    }
//
//    public boolean dfs(int i, int[] nums, int temp_sum, int sum) {
//        if (i < 0) {
//            if (temp_sum * 2 == sum) {
//                return true;
//            } else {
//                return false;
//            }
//        }
//
//        if (temp_sum * 2 == sum) {
//            return true;
//        }
//        return dfs(i - 1, nums, temp_sum - nums[i], sum) || dfs(i - 1, nums, temp_sum, sum);
//    }

//    /*
//    这种想法不正确，子集中的元素不一定有序
//     */
//    public boolean canPartition(int[] nums) {
//        Arrays.sort(nums);
//        int[] pre_sum = new int[nums.length];
//        int[] latter_sum = new int[nums.length];
//        pre_sum[0] = nums[0];
//        for (int i = 1; i < nums.length; i++) {
//            pre_sum[i] = pre_sum[i - 1] + nums[i];
//        }
//        latter_sum[nums.length - 1] = nums[nums.length - 1];
//        for (int i = nums.length - 2; i >= 0; i--) {
//            latter_sum[i] = latter_sum[i + 1] + nums[i];
//        }
////        System.out.println(Arrays.toString(pre_sum));
////        System.out.println(Arrays.toString(latter_sum));
//        HashSet<Integer> set = new HashSet<>(nums.length - 1);
//        for (int i = 0; i < pre_sum.length - 1; i++) {
//            set.add(pre_sum[i]);
//        }
//        for (int i = 1; i < latter_sum.length; i++) {
//            if (set.contains(latter_sum[i])) {
//                return true;
//            }
//        }
//        return false;
//    }

}
